package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author hanjuntao
 * @date 2025/8/27 0027
 */
public class L_145_二叉树的后序遍历 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        //       1
        //      2  3
        //    4   5

        System.out.println(postorderTraversal2(root));  // [4,5,2,3,1]
    }

    /**
     * 递归
     *
     * @param root
     * @return
     */
    public static List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<Integer> result = new ArrayList<>();
        post(root, result);
        return result;
    }

    private static void post(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        post(root.left, result);
        post(root.right, result);
        result.add(root.val);
    }

    /**
     * 迭代
     * <p>
     * 先访问左子树，再访问右子树，最后访问根结点
     * <p>
     * 1. 初始化一个栈，将根节点入栈。同时设置一个指针prev用于记录上一个访问的节点。
     * 2. 当栈不为空时，取出栈顶节点（不弹出）：
     * a. 如果当前节点是叶子节点，或者当前节点的右子树已经访问过（即prev等于当前节点的右节点，且右节点不为空）或者左子树已经访问过（且右节点为空），则访问当前节点，并出栈，同时设置prev为当前节点。
     * b. 否则，如果当前节点的右子树存在，则先将右子树入栈；如果左子树存在，则将左子树入栈。（注意：因为栈是后进先出，所以先右后左，这样栈顶会是左子树，然后右子树，最后根节点）
     *
     * @param root
     * @return
     */
    public static List<Integer> postorderTraversal2(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<Integer> result = new ArrayList<>();

        TreeNode prev = null;
        Stack<TreeNode> stack = new Stack<>();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty()) {
                break;
            }

            // 需要判断栈顶节点能不能访问
            // 能访问的前提是其左右子树都被访问过
            // 1. 情况1：左右子树都为空
            // 2. 情况2：右子树为空
            // 3. 情况3：最近访问的是左子树的根节点
            // 满足这三种情况，证明由子树已访问过，可以访问根节点
            root = stack.peek();
            if ((root.left == null && root.right == null) || root.right == null || root.right == prev) {
                root = stack.pop();
                result.add(root.val);
                prev = root;
                root = null;
            } else {
                // 访问右子树
                root = root.right;
            }
        }

        return result;
    }
}
